/*
A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.
*/

class Solution {
public:
    int numDecodings(string s) {
        if (!s.length() || s[0] == '0') return 0;
        else if (s.length() == 1) return 1;
        int num, n_pprev = 1, n_prev = 1; // first char
        for (int i = 1; i < s.length(); i++) {
            num = 0;
            if (s[i] != '0') num += n_prev;
            if (s[i-1] == '1' || (s[i-1] == '2' && s[i] <= '6')) num+= n_pprev;
            if (!num) return num; // invalid string
            n_pprev = n_prev; n_prev = num;
        }
        return num;
    }
};

#if 0
class Solution {
public:
    int numDecodings(string s) {
        if (!s.length() || s[0] == '0') return 0;
        else if (s.length() == 1) return 1;
        // more than one char
        int l_cur=0, l_pprev=1, l_prev=1; // first char
        for (int i = 1; i < s.length(); i++) {
            if (s[i] == '0') {
                if (s[i-1] != '1' && s[i-1] != '2') return 0; // invalid
                else l_cur = l_pprev;
            } else {
                l_cur = l_prev + ((IsValid(s[i-1], s[i]))?l_pprev:0);
            }
            l_pprev = l_prev;
            l_prev = l_cur;
        }
        return l_cur;
    }
private:
    bool IsValid(char c1, char c2) {
        if (c1 == '0' || c1 > '2') return false;
        else if (c1 == '2' && c2 > '6') return false;
        return true;
    }
};
#endif
